package com.atwy.tree;

/**
 * 二叉树案例，
 * 1、前序遍历、中序遍历、后续遍历
 * 2、查找，通过前序遍历、中序遍历、后续遍历进行查找
 * 3、删除，
 * 1)如果删除的是叶子节点，则删除该节点。
 * 2)如果删除的是非叶子节点，则删除该子树。
 */
public class BinaryTreeDemo {
    public static void main(String[] args) {
        // 1.先创建几个节点,静态创建
        TressNode node = new TressNode(1, "宋江");
        TressNode node2 = new TressNode(2, "吴用");
        TressNode node3 = new TressNode(3, "卢俊义");
        TressNode node4 = new TressNode(4, "林冲");
        TressNode node5 = new TressNode(5, "关胜");

        //2.将各节点连接起来
        node.setLeft(node2);
        node.setRight(node3);

        node3.setLeft(node5);
        node3.setRight(node4);

        // 3.二叉树构建
        BinaryTree tree = new BinaryTree(node);

        // 4.遍历二叉树
        System.out.println("前序遍历开始...");
        tree.preOrder();
        System.out.println("前序遍历结束...");

        System.out.println("中序遍历开始...");
        tree.middleOrder();
        System.out.println("中序遍历结束...");

        System.out.println("后序遍历开始...");
        tree.postOrder();
        System.out.println("后序遍历结束...");

        // 5.二叉树查找
        System.out.println("前序遍历方式查找...");
        TressNode result = tree.preOrderSearch(5);
        if (result != null) {
            System.out.println("找到目标，目标为：" + result);
        } else {
            System.out.println("没找到");
        }

        System.out.println("中序遍历方式查找...");
        TressNode result2 = tree.middleOrderSearch(5);
        if (result2 != null) {
            System.out.println("找到目标，目标为：" + result2);
        } else {
            System.out.println("没找到");
        }

        System.out.println("后序遍历方式查找...");
        TressNode result3 = tree.postOrderSearch(5);
        if (result3 != null) {
            System.out.println("找到目标，目标为：" + result3);
        } else {
            System.out.println("没找到");
        }

        // 6.二叉树的删除
        System.out.println("删除操作开始~");
        tree.deleteNode(5);
        System.out.println("删除操作结束，现在的树前序遍历是：");
        tree.preOrder();

    }
}

/**
 * 二叉树
 */
class BinaryTree {
    // 树根
    TressNode root;

    public BinaryTree(TressNode root) {
        this.root = root;
    }

    /**
     * 前序遍历，根-左-右
     */
    public void preOrder() {
        if (this.root == null) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        this.root.preOrder();
    }

    /**
     * 中序遍历，左-根-右
     */
    public void middleOrder() {
        if (this.root == null) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        this.root.middleOrder();
    }

    /**
     * 后续遍历，左-右-根
     */
    public void postOrder() {
        if (this.root == null) {
            System.out.println("二叉树为空，无法遍历");
            return;
        }
        this.root.postOrder();
    }

    public TressNode preOrderSearch(int no) {
        if (this.root != null) {
            return this.root.preOrderSearch(no);
        }
        System.out.println("二叉树为空，无法遍历");
        return null;
    }

    public TressNode middleOrderSearch(int no) {
        if (this.root != null) {
            return this.root.middleOrderSearch(no);
        }
        System.out.println("二叉树为空，无法遍历");
        return null;
    }

    public TressNode postOrderSearch(int no) {
        if (this.root != null) {
            return this.root.postOrderSearch(no);
        }
        System.out.println("二叉树为空，无法遍历");
        return null;
    }

    public void deleteNode(int no) {
        if (this.root == null) {
            System.out.println("二叉树为空");
            return;
        }
        if (this.root.getVal() == no) {
            this.root = null;
            return;
        }
        // 递归删除
        this.root.deleteNode(no);
    }
}

/**
 * 节点
 */
class TressNode {
    private int val;
    private String name;
    private TressNode left;
    private TressNode right;

    public TressNode(int val, String name) {
        this.val = val;
        this.name = name;
    }

    /**
     * 前序遍历，根-左-右
     */
    public void preOrder() {
        // 根
        System.out.println(this);
        // 左
        if (this.left != null) {
            this.left.preOrder();
        }
        // 右
        if (this.right != null) {
            this.right.preOrder();
        }
    }

    /**
     * 中序遍历，左-根-右
     */
    public void middleOrder() {
        // 左
        if (this.left != null) {
            this.left.middleOrder();
        }
        // 根
        System.out.println(this);

        // 右
        if (this.right != null) {
            this.right.middleOrder();
        }
    }


    /**
     * 后续遍历，左-右-根
     */
    public void postOrder() {
        // 左
        if (this.left != null) {
            this.left.postOrder();
        }
        // 右
        if (this.right != null) {
            this.right.postOrder();
        }
        // 根
        System.out.println(this);
    }

    /**
     * 前序查找
     *
     * @param no
     * @return
     */
    public TressNode preOrderSearch(int no) {
        System.out.println("前序查找~");
        // 比较当前节点是否是目标
        if (no == this.val) {
            return this;
        }

        TressNode result = null;
        if (this.left != null) {// 左
            result = this.left.preOrderSearch(no);
        }
        if (result != null) {
            return result;
        }
        if (this.right != null) {// 右
            result = this.right.preOrderSearch(no);
        }
        return result;
    }

    /**
     * 中序查找
     *
     * @param no
     * @return
     */
    public TressNode middleOrderSearch(int no) {
        TressNode result = null;
        if (this.left != null) {// 左
            result = this.left.middleOrderSearch(no);
        }
        if (result != null) {
            return result;
        }
        System.out.println("中序查找~");
        // 比较当前节点是否是目标
        if (no == this.val) {
            return this;
        }

        if (this.right != null) {// 右
            result = this.right.middleOrderSearch(no);
        }
        return result;
    }

    /**
     * 后序查找
     *
     * @param no
     * @return
     */
    public TressNode postOrderSearch(int no) {
        TressNode result = null;
        if (this.left != null) {// 左
            result = this.left.postOrderSearch(no);
        }
        if (result != null) {
            return result;
        }

        if (this.right != null) {// 右
            result = this.right.postOrderSearch(no);
        }
        if (result != null) {
            return result;
        }
        System.out.println("后续查找~");
        // 比较当前节点是否是目标
        if (no == this.val) {
            return this;
        }

        return null;
    }

    /**
     * 删除操作是去判断左右子树是否满足要求。否则试想下如果当前节点是要删除的，在该方法中如何删除呢
     *
     * @param no
     */
    public void deleteNode(int no) {

        if (this.left != null && this.left.val == no) {
            this.left = null;
            return;
        }
        if (this.right != null && this.right.val == no) {
            this.right = null;
            return;
        }

        if (this.left != null) {// 左不为null，左递归删除
            this.left.deleteNode(no);
        }
        if (this.right != null) {// 右不为null，右递归删除
            this.right.deleteNode(no);
        }
    }


    public int getVal() {
        return val;
    }

    public void setVal(int val) {
        this.val = val;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public TressNode getLeft() {
        return left;
    }

    public void setLeft(TressNode left) {
        this.left = left;
    }

    public TressNode getRight() {
        return right;
    }

    public void setRight(TressNode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder("TressNode{");
        sb.append("val=").append(val);
        sb.append(", name='").append(name).append('\'');
        sb.append('}');
        return sb.toString();
    }
}
